package LeetCode;

public class LC_459_RepeatedSubstringPattern {

    public static void main(String[] args) {

    }


    public class Solution {
        public boolean repeatedSubstringPattern(String str) {
            int[] prefix = build(str);
            int n = str.length();
            return prefix[n - 1] != 0 && n % (n - prefix[n - 1]) == 0;
        }

        private int[] build(String s) {
            int n = s.length();
            int[] res = new int[n];
            int i = 1, j = 0;
            while (i < n) {
                if (s.charAt(i) == s.charAt(j)) {
                    res[i] = j + 1;
                    i++;
                    j++;
                } else {
                    if (j == 0) i++;
                    else j = res[j - 1];
                }
            }
            return res;
        }

    }
}